{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{- # LANGUAGE FlexibleInstances # -}
module Container where

data Abb a b = Branch a b (Abb a b) (Abb a b) | Leaf

class Container c a b |c->a, c->b where

empty :: c
add :: c -> a -> b -> c
search :: c -> a -> Maybe b
--del :: c -> a -> c
--toListPair :: c -> [(a,b)]

--instance (Ord a) => Container (Abb a b)a b where
--empty = abb_empty
--add x y xs = abb_add x y xs
--search x xs = abb_search x xs
--del x xs = abb_del x xs
--toListPair xs = abb_toListPair xs

instance (Ord a) => Container (Abb a b) a b where

empty = Leaf

add Leaf x y = Branch x y Leaf Leaf
add arb@(Branch ni nd ri rd) x y
       |x == ni = arb
       |x > ni = Branch ni nd ri (add rd x y)
       |otherwise = Branch ni nd (add ri x y) rd

search Leaf x = Nothing
search (Branch ni nd ri rd) x
       |x == ni = Just nd
       |x > ni = search rd x
       |x < ni = search ri x


